String Matching
String Matching হলো একটি টেক্সটে একটি নির্দিষ্ট প্যাটার্ন খুঁজে বের করার প্রক্রিয়া। এটি বিভিন্ন বাস্তব জীবনের অ্যাপ্লিকেশনগুলিতে ব্যবহৃত হয়, যেমন টেক্সট এডিটর, সার্চ ইঞ্জিন, এবং ডেটাবেস অনুসন্ধান।
প্রধান অ্যালগরিদম
Naive String Matching Algorithm:
- এটি সবচেয়ে সহজ পদ্ধতি। এটি প্রতিটি পজিশনে প্যাটার্নের সাথে টেক্সটের তুলনা করে।
- সময় জটিলতা হলো \(O(n \cdot m)\), যেখানে \(n\) হলো টেক্সটের দৈর্ঘ্য এবং \(m\) হলো প্যাটার্নের দৈর্ঘ্য।
উদাহরণ:
def naive_string_matching(text, pattern):
n = len(text)
m = len(pattern)
for i in range(n - m + 1):
if text[i:i + m] == pattern:
print(f"Pattern found at index {i}")
text = "abcdeabc"
pattern = "abc"
naive_string_matching(text, pattern)
Knuth-Morris-Pratt (KMP) Algorithm:
- KMP অ্যালগরিদম একটি উন্নত পদ্ধতি যা তুলনা করার সময় পূর্ববর্তী তুলনাগুলি ব্যবহার করে পুনরাবৃত্তি কমায়।
- এটি একটি প্রি-প্রসেসিং স্টেপ ব্যবহার করে একটি লংগ্রেড টেবিল তৈরি করে, যা টেক্সট এবং প্যাটার্নের মধ্যে মেলানোর সময় সাহায্য করে।
- সময় জটিলতা হলো \(O(n + m)\).
KMP Implementation:
def kmp_search(text, pattern):
def compute_lps(pattern):
lps = [0] * len(pattern)
length = 0
i = 1
while i < len(pattern):
if pattern[i] == pattern[length]:
length += 1
lps[i] = length
i += 1
else:
if length != 0:
length = lps[length - 1]
else:
lps[i] = 0
i += 1
return lps
lps = compute_lps(pattern)
i = j = 0
while i < len(text):
if pattern[j] == text[i]:
i += 1
j += 1
if j == len(pattern):
print(f"Pattern found at index {i - j}")
j = lps[j - 1]
elif i < len(text) and pattern[j] != text[i]:
if j != 0:
j = lps[j - 1]
else:
i += 1
text = "abcdeabc"
pattern = "abc"
kmp_search(text, pattern)
Travelling Salesman Problem (TSP)
Travelling Salesman Problem (TSP) হলো একটি ক্লাসিক্যাল অপ্টিমাইজেশন সমস্যা, যেখানে একজন বিক্রেতাকে বিভিন্ন শহরে সফর করতে হয় এবং প্রতিটি শহর একবার করে সফর করে শেষে প্রথম শহরে ফিরে আসতে হয়। উদ্দেশ্য হলো মোট ভ্রমণের দূরত্ব বা খরচকে সর্বনিম্ন করা।
মূল অ্যালগরিদম
Brute Force:
- এটি সমস্ত সম্ভাব্য রুট পরীক্ষা করে এবং সর্বনিম্ন দূরত্ব বের করে।
- সময় জটিলতা হলো \(O(n!)\), যেখানে \(n\) হলো শহরের সংখ্যা।
উদাহরণ:
import itertools
def calculate_distance(route, distance_matrix):
total_distance = 0
for i in range(len(route) - 1):
total_distance += distance_matrix[route[i]][route[i + 1]]
total_distance += distance_matrix[route[-1]][route[0]] # return to start
return total_distance
distance_matrix = [[0, 10, 15, 20],
[10, 0, 35, 25],
[15, 35, 0, 30],
[20, 25, 30, 0]]
cities = list(range(len(distance_matrix)))
min_distance = float('inf')
best_route = []
for route in itertools.permutations(cities):
current_distance = calculate_distance(route, distance_matrix)
if current_distance < min_distance:
min_distance = current_distance
best_route = route
print(f"Minimum distance: {min_distance}, Best route: {best_route}")
Dynamic Programming:
- DP ব্যবহার করে TSP কে কার্যকরভাবে সমাধান করা সম্ভব।
- এটি একটি টেবিল ব্যবহার করে যেখান থেকে পূর্ববর্তী ফলাফলগুলি নেওয়া হয়, যা গতি বাড়ায়।
- সময় জটিলতা হলো \(O(n^2 \cdot 2^n)\)।
DP Implementation:
import sys
def tsp_dp(distance_matrix):
n = len(distance_matrix)
dp = [[sys.maxsize] * (1 << n) for _ in range(n)]
dp[0][1] = 0 # Start from city 0
for mask in range(1 << n):
for u in range(n):
if mask & (1 << u):
for v in range(n):
if mask & (1 << v) == 0:
dp[v][mask | (1 << v)] = min(dp[v][mask | (1 << v)], dp[u][mask] + distance_matrix[u][v])
return min(dp[i][(1 << n) - 1] + distance_matrix[i][0] for i in range(1, n))
distance_matrix = [[0, 10, 15, 20],
[10, 0, 35, 25],
[15, 35, 0, 30],
[20, 25, 30, 0]]
min_distance = tsp_dp(distance_matrix)
print(f"Minimum distance: {min_distance}")
সারসংক্ষেপ
- String Matching: টেক্সট এবং প্যাটার্ন খোঁজার জন্য বিভিন্ন অ্যালগরিদম (Naive, KMP) রয়েছে।
- Travelling Salesman Problem (TSP): বিক্রেতার সফর পরিকল্পনার জন্য ব্রুট ফোর্স এবং ডাইনামিক প্রোগ্রামিং অ্যালগরিদম ব্যবহার করা হয়।
Content added By
